package ACWing.Dynamicprogramming;
//282. 石子合并

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/13 22:05
 */
public class StonesMerge {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n+1];
        int[]sum=new int[n+1];
        for (int i = 1; i < n+1; i++) {
            arr[i]=sc.nextInt();
            sum[i]=arr[i]+sum[i-1];//前缀合用来计算最后一次合并的代价
        }
        int[][]dp=new int[n+1][n+1];
        for (int i = 2; i < n+1; i++) {//表示数组长度
            for (int j = 1; j <= n-i+1; j++) {//表示起始起点
                int l=j,r=j+i-1;
                dp[l][r]=(int)1.0E8;
                for (int k = l; k < r; k++) {
                    dp[l][r]=Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
                }
            }
        }

        System.out.println(dp[1][n]);
    }

}
